1. Field of the Invention
This invention relates to network flow policy enforcement in general, more particularly to verification of rule sets.
2. Description of the Related Art
Fast and scalable packet classification is frequently employed to enforce data flow policies in network topologies. Occasionally, two or more individual flow policy rules may conflict possibly causing violations to overall, high-level data flow policies. One algorithm for detecting such a conflict between two k-tuple filters creates a new packet filter when any conflict occurs as opposed to prioritizing filters. This algorithm may generally work for cyclic rule graphs as well, but may be slow, with O(N^2) number of rules. Also, the total number of rules may increase exponentially with the number of rule conflicts, which may be a severe limitation in classifiers with limited space for rule tables.
Another common algorithm uses data structures for detecting rule set conflicts in time complexity O(N^(3/2)). However, this algorithm is based on rectangle geometry and may work only for a 2-dimensional case.
A different approach involves building tries for each filter field. Each level of a trie is one bit of the field. A bit vector from this trie is computed to aid in conflict detection. For a database of 20,000 rules, this algorithm may execute up to 40 times faster than a more naive implementation (O(n^2)).
Frequently, multiple administrative domains in a large-scale data center network managing multiple policies may lead to a number of problems such as:                Inefficiency. Today, multiple flow enforcement policies from multiple administrative scopes of a data center network frequently can't be integrated to allow for efficient operation of the network resources. For example, a flow enforcement policy that provides for the dropping of the packets of a network flow enforced at the server's edge may be wasteful of network resources.        Complexity. Management of multiple policies from multiple administrative scopes may be complicated and error prone.        Cost. A derivative of complexity may be increased cost. Generally, if a data center network is complex to manage, it may also be costly to operate.        